The transport of streaming media is an important means of communicating information and data. Information of many types may be communicated in this manner including audio, video and text. Providers of streaming media content transmit the content to receivers (e.g., computer, television etc.) that are often operated by end users.
An issue confronted by streaming media content providers is the optimization of the encoding and/or transport of standard-compliant video streams over lossy networks for real-time playback. Factors that impact the optimization of encoding and transmission of streaming media include available computing resources for the optimization process, and the characteristics of transmission source and network. Optimization for streaming media delivery typically involves choosing an appropriate set of discrete parameters for the encoding of media material and/or the transport of the encoded media. The set of chosen parameters often has to satisfy additional constraints, such as a total transmission bit budget. This is difficult because a large number of parameters are involved for both media source and channel, and there is a substantial interdependency of these parameters.
For general discrete parameter optimization with constraints, there are two basic approaches to choosing the right parameter set: a primal approach where the original constrained problem is solved directly, and a dual approach where the constrained problem is first transformed to an easier associated unconstrained problem. Exhaustive parameter set search is one instance of the first approach, while the Lagrangian approach is one instance of the second approach. Both approaches have been used in various forms as a means of solving the network streaming media problem outlined above.
The most straightforward instance of the primal approach for choosing the best set of parameters is through an exhaustive search. By enumerating every single available possibility, one can guarantee the identification of the optimal solution in bounded time. However, such a solution is prohibitively expensive and inefficient. For example, with 20 parameters each assuming 10 possible values, the number of cases that must be enumerated using exhaustive search techniques is 1020 which is equal to 100×1 billion×1 billion.
In the second dual approach such as Lagrangian, instead of directly evaluating the different cases, the original constrained problem is approximated by a corresponding unconstrained problem where penalty function(s) are added to the objective function of the original problem. While generally faster than the primal approach, as unconstrained problems are usually easier to solve than contrained problems, dual approach like the Lagrangian relaxation has two important drawbacks that limit their applications for streaming media applications. First, dual approaches using penalty functions will converge to a good answer only when some additional assumptions on the characteristics of the objective function and/or the penalty functions are met which generally limit its application. Second, there is no easy way to select a good penalty function, and iteratively searching for one means no bound on how fast the solutions converge. Specifically, given a desired amount of computation, the quality of the solution cannot be determined a priori. Conversely, given a desired quality of solution, the amount of computation cannot be determined a priori.
Dynamic programming is a very efficient and structured technique to efficiently perform exhaustive search for many optimization problems. It is not generally applicable to all optimization problems, but is relevant to many problems, such as streaming media. There are two important characteristics of dynamic programming. First, since all possible combinations are considered in a structured manner, dynamic programming guarantees the optimal set of parameters in bounded time. Second, it is possible to terminate a dynamic programming optimization at any time, and the best set of parameters that has been evaluated to-date will be available. Nevertheless, it is generally impossible to determine the quality of the parameters obtained by a terminated dynamic programming procedure to the optimal set of parameter.